package com.datastructure.hashtable;

/**
 * @author: 临晖
 * @date: 2023/10/15
 * @description:
 */


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和（从一个数组中找到四个相加数之和，且找出来的元组于元组直接不能重复）
 */
public class Solution06 {


    /**
     *
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * 你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        //排序
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > 0) {  //排序过后，第一个数都大于零了，那肯定不会有相加等于零的情况
                break;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {      //如果当前元组的i和上一个元组的i相等，那么要么找不到，要么找到了也是和上一个元组相同，所以直接跳过
                continue;
            }


            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;

                } else if(sum < 0) {
                    left++;

                } else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left  < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }

                //

            }

        }

        return ans;
    }


    /**
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
     * 0 <= a, b, c, d < n
     * a、b、c 和 d 互不相同
     * nums[a] + nums[b] + nums[c] + nums[d] == target
     * 你可以按 任意顺序 返回答案 。
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();


        for (int i = 0; i < nums.length; i++) {
            //一级剪枝
            if (nums[i] > target && (nums[i] > 0 || target > 0)) {
                return ans;
            }

            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                //二级剪枝，这里不能使用return，这里只能代表当前循环结束
                if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) {
                    break;
                }

                //去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                //双指针移动
                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }

                        left++;
                        right--;
                    }
                }


            }
        }
        return ans;
    }

}
